package homework3;

import java.util.Random;

/**
 * Sorting algorithms comparison class
 * 
 * @author eDisOn  SN:2009212634  Email:lilh09@mails.tsinghua.edu.cn
 *
 */
public class SortingAlgorithm
{
	private int[] randomize(int n)
	{
		Random rand = new Random();

		long start = System.currentTimeMillis();
		int tmp;
		int[] array = new int[n];
		for (int i = 0; i < n; i++)
		{
			// if rand.nextBoolean() == true, generate number between 0 ~ 2^32-1
			if (rand.nextBoolean())
			{
				array[i] = rand.nextInt(Integer.MAX_VALUE);
			}
			else
			// else generate number between -2^32 ~ -1
			{
				tmp = rand.nextInt(Integer.MAX_VALUE - 1) + 1;
				array[i] = ~tmp + 1;
			}
		}
		long end = System.currentTimeMillis();
		System.out.println("Random number genereate time : " + (end - start)
				+ "(ms)");
		return array;
	}

	public void insertionSort(int[] array)
	{
		int item;
		int i, j;
		for (i = 1; i < array.length; i++)
		{
			item = array[i];
			j = i - 1;
			while (j >= 0)
			{
				if (array[j] > item)
				{
					array[j + 1] = array[j];
					j--;
				}
				else
				{
					break;
				}
			}
			array[j + 1] = item;
		}
	}

	public void quickSort(int[] array, int start, int end)
	{
		if (start < end)
		{
			int p = partition(array, start, end);
			quickSort(array, start, p - 1);
			quickSort(array, p + 1, end);
		}
	}

	private int partition(int[] array, int start, int end)
	{
		int tmp, cmp = array[end];
		int i = start - 1, j = start;

		while (j < end)
		{
			if (array[j] < cmp)
			{
				tmp = array[j];
				array[j] = array[i + 1];
				array[i + 1] = tmp;
				i++;
			}
			j++;
		}
		tmp = array[end];
		array[end] = array[i + 1];
		array[i + 1] = tmp;

		return i + 1;
	}

	public void mergeSort(int[] array, int start, int end)
	{
		if (start < end)
		{
			int mid = (start + end) >>> 1;

			mergeSort(array, start, mid);
			mergeSort(array, mid + 1, end);

			// copy sub-array
			int[] leftArr = new int[mid - start + 1];
			for (int i = 0; i < leftArr.length; i++)
			{
				leftArr[i] = array[i + start];
			}

			int[] rightArr = new int[end - mid];
			for (int i = 0; i < rightArr.length; i++)
			{
				rightArr[i] = array[i + mid + 1];
			}

			// merge
			int i = 0, j = 0, index = start;
			while ((i < leftArr.length) && (j < rightArr.length))
			{
				if (leftArr[i] <= rightArr[j])
				{
					array[index++] = leftArr[i++];
				}
				else
				{
					array[index++] = rightArr[j++];
				}
			}
			if (i == leftArr.length)
			{
				while (j < rightArr.length)
				{
					array[index++] = rightArr[j++];
				}
			}
			else
			{
				while (i < leftArr.length)
				{
					array[index++] = leftArr[i++];
				}
			}
		}
	}

	public int[] radixSort(int[] array, int bitRange)
	{
		// because MAX_VALUE of int is 2^31-1, so bitRange must <= 31

		int startBit = 0, endBit = 0;
		while ((endBit = startBit + bitRange - 1) <= 31)
		{
			array = countingSort(array, startBit, endBit);
			startBit = endBit + 1;
		}
		if (startBit <= 31)
		{
			array = countingSort(array, startBit, 31);
		}
		return array;
	}

	private int[] countingSort(int[] array, int startBit, int endBit)
	{
		// bit index begin with 0
		int[] result = new int[array.length];

		// because MAX_VALUE of int is 2^31-1, so (endBit - startBit + 1) must
		// <=31
		int counterNum = 1 << (endBit - startBit + 1);
		int[] counter = new int[counterNum];

		long L = (long) Math.pow(2, endBit + 1) - 1;
		// System.out.println(Long.toBinaryString(L));
		L = L >> startBit;
		// System.out.println(Long.toBinaryString(L));
		L = L << startBit;
		// System.out.println(Long.toBinaryString(L));

		// calculate count
		for (int i = 0; i < array.length; i++)
		{
			long value = array[i] + (long) Integer.MAX_VALUE;

			// System.out.println(Long.toBinaryString(value));

			value = value & L;

			// System.out.println(Long.toBinaryString(value));

			value = value >> startBit;

			// System.out.println(Long.toBinaryString(value));

			counter[(int) value]++;
		}

		// merge count
		for (int i = 1; i < counter.length; i++)
		{
			counter[i] = counter[i - 1] + counter[i];
		}

		// sort array according to count
		for (int i = array.length - 1; i >= 0; i--)
		{
			long value = array[i] + Integer.MAX_VALUE;
			value = value & L;
			value = value >> startBit;

			result[counter[(int) value] - 1] = array[i];
			counter[(int) value]--;
		}

		// copy back
		return result;
	}

	public void runInsertionSort(int[] array, int num)
	{
		Random rand = new Random();
		long minimum, middle, maximum;
		for (int i = 0; i < array.length; i++)
		{
			int swapPos = rand.nextInt(array.length - i) + i;

			int tmp = array[i];
			array[i] = array[swapPos];
			array[swapPos] = tmp;
		}

		long insertionStart = System.currentTimeMillis();
		insertionSort(array);
		long insertionEnd = System.currentTimeMillis();

		System.out.print("Insertion Sort\t[");
		minimum = (long) array[0] + (long) Integer.MAX_VALUE;
		System.out.print("Minimum : " + minimum + "\t");
		middle = (long) array[num >> 1] + (long) Integer.MAX_VALUE;
		System.out.print("Middle : " + middle + "\t");
		maximum = (long) array[num - 1] + (long) Integer.MAX_VALUE;
		System.out.print("Maximum : " + maximum + "\t");
		System.out.println("Time : " + (insertionEnd - insertionStart) + "]");
	}

	public void runQuickSort(int[] array, int num)
	{
		Random rand = new Random();
		long minimum, middle, maximum;
		for (int i = 0; i < array.length; i++)
		{
			int swapPos = rand.nextInt(array.length - i) + i;

			int tmp = array[i];
			array[i] = array[swapPos];
			array[swapPos] = tmp;
		}

		long quickStart = System.currentTimeMillis();
		quickSort(array, 0, array.length - 1);
		long quickEnd = System.currentTimeMillis();

		System.out.print("Quicksort\t[");
		minimum = (long) array[0] + (long) Integer.MAX_VALUE;
		System.out.print("Minimum : " + minimum + "\t");
		middle = (long) array[num >> 1] + (long) Integer.MAX_VALUE;
		System.out.print("Middle : " + middle + "\t");
		maximum = (long) array[num - 1] + (long) Integer.MAX_VALUE;
		System.out.print("Maximum : " + maximum + "\t");
		System.out.println("Time : " + (quickEnd - quickStart) + "]");
	}

	public void runMergeSort(int[] array, int num)
	{
		Random rand = new Random();
		long minimum, middle, maximum;
		for (int i = 0; i < array.length; i++)
		{
			int swapPos = rand.nextInt(array.length - i) + i;

			int tmp = array[i];
			array[i] = array[swapPos];
			array[swapPos] = tmp;
		}

		for (int i = 0; i < array.length; i++)
		{
			int swapPos = rand.nextInt(array.length - i) + i;

			int tmp = array[i];
			array[i] = array[swapPos];
			array[swapPos] = tmp;
		}
		long mergeStart = System.currentTimeMillis();
		mergeSort(array, 0, array.length - 1);
		long mergeEnd = System.currentTimeMillis();

		System.out.print("Merge Sort\t[");
		minimum = (long) array[0] + (long) Integer.MAX_VALUE;
		System.out.print("Minimum : " + minimum + "\t");
		middle = (long) array[num >> 1] + (long) Integer.MAX_VALUE;
		System.out.print("Middle : " + middle + "\t");
		maximum = (long) array[num - 1] + (long) Integer.MAX_VALUE;
		System.out.print("Maximum : " + maximum + "\t");
		System.out.println("Time : " + (mergeEnd - mergeStart) + "]");
	}

	public void runRadixSort(int[] array, int num)
	{
		Random rand = new Random();
		long minimum, middle, maximum;
		for (int i = 0; i < array.length; i++)
		{
			int swapPos = rand.nextInt(array.length - i) + i;

			int tmp = array[i];
			array[i] = array[swapPos];
			array[swapPos] = tmp;
		}

		long radixStart = System.currentTimeMillis();
		array = radixSort(array, 8);
		long radixEnd = System.currentTimeMillis();

		System.out.print("Radix Sort\t[");
		minimum = (long) array[0] + (long) Integer.MAX_VALUE;
		System.out.print("Minimum : " + minimum + "\t");
		middle = (long) array[num >> 1] + (long) Integer.MAX_VALUE;
		System.out.print("Middle : " + middle + "\t");
		maximum = (long) array[num - 1] + (long) Integer.MAX_VALUE;
		System.out.print("Maximum : " + maximum + "\t");
		System.out.println("Time : " + (radixEnd - radixStart) + "]");
	}

	private void runRadixSortInPlace(int[] array, int num)
	{
		Random rand = new Random();
		long minimum, middle, maximum;
		for (int i = 0; i < array.length; i++)
		{
			int swapPos = rand.nextInt(array.length - i) + i;

			int tmp = array[i];
			array[i] = array[swapPos];
			array[swapPos] = tmp;
		}

		long radixInPlaceStart = System.currentTimeMillis();
		radixSortInPlace(array, 0, array.length - 1, 24, 31, 8);
		long radixInPlaceEnd = System.currentTimeMillis();

		System.out.print("Radix in Place\t[");
		minimum = (long) array[0] + (long) Integer.MAX_VALUE;
		System.out.print("Minimum : " + minimum + "\t");
		middle = (long) array[num >> 1] + (long) Integer.MAX_VALUE;
		System.out.print("Middle : " + middle + "\t");
		maximum = (long) array[num - 1] + (long) Integer.MAX_VALUE;
		System.out.print("Maximum : " + maximum + "\t");
		System.out.println("Time : " + (radixInPlaceEnd - radixInPlaceStart)
				+ "]");
	}

	public void radixSortInPlace(int[] arr, int startArr, int endArr,
			int startBit, int endBit, int bitRange)
	{
		if (startArr != endArr)
		{
			int counterNum = 1 << (endBit - startBit + 1);
			int[] counter = new int[counterNum];
			int[] lengthCounter = new int[counterNum];
			int[] bakCounter = new int[counterNum];

			long L = (long) Math.pow(2, endBit + 1) - 1;
			L = L >> startBit;
			L = L << startBit;

			// calculate count
			for (int i = startArr; i < endArr + 1; i++)
			{
				long value = arr[i] + (long) Integer.MAX_VALUE;

				value = value & L;

				value = value >> startBit;

				counter[(int) value]++;
			}

			// merge count
			lengthCounter[0] = counter[0];
			bakCounter[0] = counter[0];
			for (int i = 1; i < counter.length; i++)
			{
				lengthCounter[i] = counter[i];
				counter[i] = counter[i - 1] + counter[i];
				bakCounter[i] = counter[i];
			}

			// sort in place
			long value;
			int index = endArr;
			while (index >= startArr)
			{
				value = arr[index] + (long) Integer.MAX_VALUE;
				value = value & L;
				value = value >> startBit;

				int limit = bakCounter[(int) value] + startArr - 1;

				int desirePos = counter[(int) value] + startArr - 1;

				if (index > desirePos && index <= limit)
				{
					index--;
					continue;
				}
				else
				{
					swap(arr, index, desirePos);
					counter[(int) value]--;
				}
			}

			// recursive process
			int nuEndBit = startBit - 1;
			int nuStartBit = nuEndBit - bitRange + 1;
			if (nuEndBit >= 0 && nuStartBit >= 0)
			{
				int nuStartArr = startArr;
				int nuEndArr = startArr;
				for (int i = 0; i < counter.length; i++)
				{
					int length = lengthCounter[i];
					if (length > 0)
					{
						nuEndArr = nuStartArr + length - 1;
						radixSortInPlace(arr, nuStartArr, nuEndArr, nuStartBit,
								nuEndBit, bitRange);
						nuStartArr = nuEndArr + 1;
					}
				}
			}
			else if (nuEndBit >= 0 && nuStartBit < 0)
			{
				nuStartBit = 0;
				int nuStartArr = startArr;
				int nuEndArr = startArr;
				for (int i = 0; i < counter.length; i++)
				{
					int length = lengthCounter[i];
					if (length > 0)
					{
						nuEndArr = nuStartArr + length - 1;
						radixSortInPlace(arr, nuStartArr, nuEndArr, nuStartBit,
								nuEndBit, bitRange);
						nuStartArr = nuEndArr + 1;
					}
				}
			}
		}
	}

	private void swap(int[] arr, int pos1, int pos2)
	{
		try
		{
			int tmp = arr[pos1];
			arr[pos1] = arr[pos2];
			arr[pos2] = tmp;
		}
		catch (Exception ex)
		{
			System.out.println(pos1 + "\t" + pos2);
		}
	}

	public static void main(String args[]) throws InterruptedException
	{
		SortingAlgorithm sortor = new SortingAlgorithm();

		for (int i = 1; i < 9; i++)
		{
			int num = (int) (1 * (int) Math.pow(10, i));
			System.err.println(">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>num = " + num
					+ ">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>");
			int[] array = sortor.randomize(num);

			if (num < 100000)
				sortor.runInsertionSort(array, num);

			sortor.runQuickSort(array, num);

			sortor.runMergeSort(array, num);

			sortor.runRadixSort(array, num);

			sortor.runRadixSortInPlace(array, num);

			Thread.sleep(1000);
		}
	}
}
